UVa/497 - Strategic defense initiative/497.cpp

   1 #include <iostream>
   2 #include <sstream>
   3 #include <vector>
   4 #include <cassert>
   5 #include <iterator>
   6
   7 using namespace std;
   8
   9 void print(vector<int> &a, vector<int> &p, const int &i){
  10   if (p[i] != -1){
  11     print(a, p, p[i]);
  12   }
  13   cout << a[i] << endl;
  14 }
  15
  16 int main(){
  17   int casos;
  18   cin >> casos; while (getchar() != '\n');
  19   string s;
  20   getline(cin, s);
  21   bool first = true;
  22   while (casos--){
  23     if (!first) cout << endl;
  24     first = false;
  25     vector<int> a;
  26     while (getline(cin, s) && s != ""){
  27       stringstream ss(s);
  28       int x;
  29       ss >> x;
  30       a.push_back(x);
  31     }
  32     assert(a.size() > 0);
  33     vector<int> p(a.size());
  34     vector<int> dp(a.size());
  35     for (int i=0; i<a.size(); ++i){
  36       p[i] = -1;
  37       dp[i] = 1;
  38       //      cout << "i es: " << i << endl;
  39       for (int j=0; j<i; ++j){
  40         //cout << "  j es: " << j << endl;
  41         if (a[i] > a[j] && dp[j] + 1 > dp[i]){
  42           dp[i] = dp[j] + 1;
  43           p[i] = j;
  44         }
  45       }
  46     }
  47
  48     //    cout << "a es: "; copy(a.begin(), a.end(), ostream_iterator<int>(cout, " "));
  49     //    cout << endl;
  50
  51     //    cout << "dp es: "; copy(dp.begin(), dp.end(), ostream_iterator<int>(cout, " "));
  52     //    cout << endl;
  53
  54     int best = dp[0];
  55     int indexMax = 0;
  56     for (int i=0; i<a.size(); ++i){
  57       if (dp[i] > best){
  58         best = dp[i];
  59         indexMax = i;
  60       }
  61     }
  62     cout << "Max hits: " << best << endl;
  63     print(a, p, indexMax);
  64   }
  65   return 0;
  66 }